class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        // 这道题也是需要转化的 -> 在数组中挑选某些数，使这些数的和尽可能接近于 sum/2
        int n = stones.size(), sum = 0;
        for(int &x : stones) sum += x;
        int target = sum / 2;

        // 下面使用滚动数组进行优化
        vector<int> dp(target + 1);
        for(int i = 1; i <= n; i++)
            for(int j = target; j >= stones[i - 1]; j--)
                dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
        return sum - 2 * dp[target];

        // 这道题重要的就是转化成01背包问题
        // 比如stones是[a, b, c, d, e]，此时我选a和b一起粉碎且a<b，那么粉碎完的数组就是[b-a, c, d, e]
        // 依此类推，到最后假设数组剩的最后一个值就是[e - a + b + c - d]，转化为目标和那道题，给每个数前面添加+-使其值等于某个target
        // 假设正数为a，负数之和的绝对值为b，即求a-b的值尽可能的小，即选择a+b的一半就可以保证这个值最小
        // vector<vector<int>> dp(n + 1, vector<int>(target + 1));
        // for(int i = 1; i <= n; i++)
        // {
        //     for(int j = 0; j <= target; j++)
        //     {
        //         dp[i][j] = dp[i - 1][j];
        //         if(j >= stones[i - 1])
        //             dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
        //     }
        // }

        // return sum - 2 * dp[n][target];
    }
};